/**
 * 
 */
package dp;

/**
 * @author xyyi
 * 
 * 
 *         google-interview-questions 40 Answers A log of wood has n marks on
 *         it. Cost of cutting wood at a particular mark is proportional to the
 *         length of the cutting log. The log of wood can be cut at all the
 *         marks. Find the optimal order of the marks where the log should be
 *         cut in order to minimize the total cost of cutting. Give a array of
 *         all marks [20, 50, 80] and a length of the whole log the cost to cut
 * 
 *         http://www.careercup.com/question?id=13467664
 */
public class WoodCutting {

	/**
	 * 
	 */
	public WoodCutting() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * Dynamic programming n the size of the length of the marks array, length,
	 * the length of the log 1, add 2 extra marks at the two ends of the array n
	 * + 2 2, minCost[i][j] the minimum cost between ith and jth mark 3,
	 * minCost[i][i] = min(minCost[i][k] + minCost[k][j] + (marks[j] - mark[i]))
	 * where from k >= i + 1 to k <= j - 1 and j > i + 2 4, minCost[i][j] = 0
	 * where j = i + 1 5, minCost[i][j] = mark[j] - mark[i] where j = i + 2
	 */
	public static int minCostMemoization(int[] marks) {
		return 0;
	}

	public static int minCostDP(int[] marks) {
		return 0;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
